home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group98a.txt / 000132_icon-group-sender _Fri Mar 13 12:35:30 1998.msg < prev    next >
Internet Message Format  |  2000-09-20  |  4KB
  1. Return-Path: <icon-group-sender>
  2. Received: from kingfisher.CS.Arizona.EDU (kingfisher.CS.Arizona.EDU [192.12.69.239])
  3.     by baskerville.CS.Arizona.EDU (8.8.7/8.8.7) with SMTP id MAA14427
  4.     for <icon-group-addresses@baskerville.CS.Arizona.EDU>; Fri, 13 Mar 1998 12:35:30 -0700 (MST)
  5. Received: by kingfisher.CS.Arizona.EDU (5.65v4.0/1.1.8.2/08Nov94-0446PM)
  6.     id AA17660; Fri, 13 Mar 1998 12:35:29 -0700
  7. Message-Id: <3509869A.6F03@gte.net>
  8. Date: Fri, 13 Mar 1998 13:18:50 -0600
  9. From: Mark Evans <evans@gte.net>
  10. Reply-To: evans@gte.net
  11. Organization: None
  12. X-Mailer: Mozilla 3.01 (Win95; I)
  13. Mime-Version: 1.0
  14. To: icon-group@optima.CS.Arizona.EDU
  15. Subject: Re: Letter Probabilities
  16. References: <199803131831.KAA01976@sims-rd.corp.cirrus.com>
  17. Content-Type: text/plain; charset=us-ascii
  18. Content-Transfer-Encoding: 7bit
  19. Errors-To: icon-group-errors@optima.CS.Arizona.EDU
  20. Status: RO
  21. Content-Length: 3003
  22.  
  23. Eka,
  24.  
  25. Thank you for taking time to reply so thoughtfully.  I thought of this
  26. technique before making my post, and have two comments about it.  It is
  27. a valid approach.
  28.  
  29. (1) Some letters occur with vanishingly small, but nonzero,
  30. probabilities.  In order to handle them, the generator string would have
  31. to be extremely long just to have the letter occur once or twice in the
  32. string!  We are talking about several thousand characters in a string.
  33.  
  34. (2) There is a more elegant Icon syntax for producing a random character
  35. from a string, namely ?string.  I assume that this operator assumes
  36. equal probability for each letter in the string, namely 1/N where N =
  37. *string.
  38.  
  39.  
  40.  
  41.  
  42. What you propose is valid and I will think it through once more.  When I
  43. first rejected the idea, it was because I had the impression that Icon
  44. could not handle strings of more that 255 characters.  That appears not
  45. to be the case.
  46.  
  47. FYI, I did implement the while-loop mentioned earlier, and it is
  48. reasonably fast.  In fact I am impressed overall with the speed of Icon
  49. as an interpreted language for many of these inner nested loops.
  50.  
  51. I recall reading in one of the online archives about problems with
  52. Icon's built-in random number generator.  Such problems would affect
  53. random string access with ?.  Because I am concerned with statistical
  54. behaviors, I need to know if anyone has any information about these
  55. issues, or whether they have been solved.
  56.  
  57. Random number generators can be funny things.  I once worked for a
  58. former VP of reserach at a big aerospace concern.  He told me a story. 
  59. There was once an argument over the merits of a particular FORTRAN
  60. random number generator used in Monte Carlo simulations and
  61. integrations.  The author of this module produced all kinds of 2D and 3D
  62. scatter plots showing its random characteristics.  It would always
  63. appear to fill the space.
  64.  
  65. The man harboring suspicions ended the argument with a single plot of
  66. his own.  He had the generator produce long sequences of (x,y,z)
  67. coordinates to make another 3D scatter-plot.  This time, however, he
  68. changed the viewpoint so that the true nature of the algorithm became
  69. apparent to all.
  70.  
  71. All the points were on a 2D plane embedded in 3-space.  You had to see
  72. the plane edge-on to observe this in the scatter plot.  Funny things can
  73. happen.
  74.  
  75.  
  76.  
  77. Best regards,
  78.  
  79. Mark
  80.  
  81.  
  82.  
  83.  
  84. Eka Laiman wrote:
  85. > 
  86. > Mark Evans wrote:
  87. > > Here is a small Icon problem related to letter probabilites.
  88. > 
  89. > This is what I would do:
  90. > 
  91. > (1) Construct a string of length n where the members of the string
  92. >     are letters and the number of occurrence of each letter is
  93. >     according to the probability of letter occurrence
  94. > 
  95. > Floyd's algorithm of generating random permutation from 1 to n:
  96. > 
  97. > (1) Fill an array L such that L[i] := i
  98. > (2) every i := n to 2 by -1 do {
  99. >         t := ?i    #  generate a random index between 1 to i
  100. >         L[i] :=: L[t]   # exchange the t-th element with the last
  101. >                         # element in current sublist
  102. >     }
  103. >
  104.  
  105.  
  106.